# Массивы

_Массив_ — это упорядоченная структура, индексированный набор связанных элементов.

Массив может быть представлен в виде последовательности: \\(a\_{0}, a\_{1}, ..., a\_{n}\\), 
где \\(n\\) — целое положительное число, большее \\(1\\). Нижние подстрочные символы — это индексы. 
Одним из экземпляров этой общей последовательности является `<a,e,i,o,u>`. В этом случае \\(n = 5\\). 
Мы можем получить доступ к третьей гласной с помощью соответствующего индекса. 
Если мы назовем эту последовательность как \\(V\\), то \\(V\_{3} = i\\) при условии, что индексация начинается с \\(1\\). 
Мы могли бы использовать такие обозначения, как `V[3]`, `V(3)` или `Third(V)`. 
Если индексация начинается с 0, тогда представление \\(V\_{2} = i\\). 

Различные языки программирования используют разные стили для представления массива. 
Чтение, а также изменение элемента по заданному индексу i занимает время _O(1)_. 
Вставка элемента в i-ю позицию требует `(n−i)` сдвига и, следовательно, это _O(n−i)_; 
аналогично удаление элемента по i-му индексу занимает _O(n−i)_ времени. 
Вставка элемента в полный массив требует создания нового массива большей емкости, 
копирования всех элементов старого массива и вставки нового элемента.

```dotty
val vowels = Array('a', 'e', 'i', 'o', 'u')
// vowels: Array[Char] = Array('a', 'e', 'i', 'o', 'u')
vowels(2)
// res0: Char = 'i'
val vowelsReversed = vowels.reverse
// vowelsReversed: Array[Char] = Array('u', 'o', 'i', 'e', 'a')
vowelsReversed(2)
// res1: Char = 'i'
vowels.length
// res2: Int = 5
```

---

**Ссылки:**

- [Род Стивенс - Алгоритмы. Теория и практическое применение. Глава 4. Массивы](https://eksmo.ru/book/algoritmy-teoriya-i-prakticheskoe-primenenie-2-e-izdanie-ITD1210854)
- [Donald E. Knuth - The Art of Computer Programming, section 2.2.6](https://www-cs-faculty.stanford.edu/~knuth/taocp.html)
- [Bhim P. Upadhyaya - Data Structures and Algorithms with Scala](https://link.springer.com/book/10.1007/978-3-030-12561-5)
